/*
 * @lc app=leetcode id=466 lang=cpp
 *
 * [466] Count The Repetitions
 */

// @lc code=start
class Solution {
public:
    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
        vector<int> repeat_count(n1 + 1, 0);
        vector<int> next_idx(n1+ 1, 0);
        int j = 0;
        int count = 0;
        for (int k = 1; k <= n1; ++k) {
            for (int i = 0; i < s1.size(); ++i) {
                if (s1[i] == s2[j]){
                    j++;
                    if (j == s2.size()){
                        j = 0;
                        count++;
                    }
                }
            }
            repeat_count[k] = count;
            next_idx[k] = j;
            for (int s = 0; s < k; ++s) {
                if (next_idx[s] == j) {
                    int interval = k - s;
                    int repeat = (n1 - s) / interval;
                    int cnt = (repeat_count[k]-repeat_count[s]) *repeat;
                    int rcnt = repeat_count[s + (n1 - s) % interval];
                    return (cnt + rcnt) / n2;

                }
            }
        }
        return repeat_count[n1]/ n2;
    }
};
// @lc code=end

